import java.util.Arrays;

public class TestHeap {
    public int[] elem;
    public int usedSize;

    public TestHeap() {
        this.elem =new int[10];
    }
    //构建底层数组；
    public void initElem(int[] array){
        for(int i=0;i< array.length;i++){
            this.elem[i]=array[i];
            this.usedSize++;
        }
    }
    //构建大堆；
    public void createHeap(){
        for(int parent=(this.usedSize-1-1)/2;parent>=0;parent--){
            siftDown(parent ,usedSize);
        }
    }
    public void swap(int[] elem,int i,int j){
        int tmp=elem[i];
        elem[i]=elem[j];
        elem[j]=tmp;
    }
    //向下调整；
    //方法：1，先确定左孩子结点的下标位置；将左孩子结点的位置设为最后一个位置；
     //....2.根据左孩子结点的位置以及公式确定父亲节点的位置；
    //.....3.先比较左右孩子结点值的大小，确定最大值；
    //.....4,将左右孩子最大值与父亲节点的值进行比较；如果孩子结点的值大于父亲节点的值就进行交换；
    //.....5.完成上述步骤后更新父亲和孩子节点位置，
    public void siftDown(int parent,int usedSize){
        int child=2*parent+1;
        while(child<usedSize){
            if(child+1<usedSize&&elem[child]<elem[child+1]){
                child++;
            }
            if(elem[child]>elem[parent]){
                swap(elem,child,parent );
                parent=child;
                child=(parent+1)*2;
            }else{
                break;
            }
        }
        
    }
    //插入元素；
    //前提;在大根堆的前提下，进行插入元素；
    //向上插入法的运用；
    //.方法；1.首先从尾部进行向上插入
    // 。。。2.根据孩子结点的位置找父亲节点的位置；
    // 。。。3，完后比较孩子与父亲节点的值，进行交换；
    // 。。。4.重新赋值孩子结点与父亲节点的位置；
    public boolean isFull(){
        return usedSize==elem.length;
    }
    public void offer(int val){
        if(isFull()){
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize]=val;
        //向上调整；
        siftUp(usedSize);
        usedSize++;
    }
    //向上调整；
    public void siftUp(int child){
        int parent=(child-1)/2;
        while(parent>=0){
            if(elem[child]>elem[parent]){
                swap(elem,child,parent);
                child=parent;
                parent=(child-1)/2;
            }else{
                break;
            }
        }
    }
//删除堆头中元素；
    //方法：将堆头元素与队尾元素进行交换；
    //。。。2.进行向下牌序；（不考虑最后一个位置）；
    ///....3.堆元素总数减一；
    public int poll(){
        if(isEmpty()){
            return -1;
        }
        int val=elem[0];
        swap(elem,0,usedSize-1);
        siftDown(0,usedSize-1);
        usedSize--;
        return val;
    }
    public boolean isEmpty(){
        return usedSize==0;
    }
}
